package lc.q250_300;

public class Q268 {

    public static void main(String[] args) {
        Q268 q268 = new Q268();
        System.out.println(q268.missingNumber3(new int[]{
                9,6,4,2,3,5,7,0,1
        }));
    }

    public int missingNumber3(int[] nums) {
        // 将0..n加起来减去所有nums的数加起来即可
        int rm = 0;
        for (int i = 0; i < nums.length; i++) {
            rm +=  i - nums[i];
        }
        rm += nums.length;
        return rm;
    }

    public int missingNumber2(int[] nums) {
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        for (int i = 0; i < nums.length + 1; i++) {
            xor ^= i;
        }
        return xor;
    }

    public int missingNumber(int[] nums) {
        // 改成常数项，那就做两次亦或运算

        int[] r = new int[nums.length + 1];
        for (int num : nums) {
            r[num] = num;
        }
        for (int i = 0; i < r.length; i++) {
            if (r[i] != i) return i;
        }
        return 0;
    }
}
